SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Covering problems</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Covering problems</span></span>

</h1>

</header>

<p>In <a href="Combinatorics" title="Combinatorics">combinatorics</a> and <a href="Computer_science" title="Computer science">computer science</a>, <b>covering problems</b> are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that. Covering problems are <a href="Optimization_(mathematics)" class="mw-redirect" title="Optimization (mathematics)">minimization problems</a> and usually <a href="Integer_linear_programs" class="mw-redirect" title="Integer linear programs">integer linear programs</a>, whose <a href="Dual_problem" class="mw-redirect" title="Dual problem">dual problems</a> are called <a href="Packing_problems" title="Packing problems">packing problems</a>.

</p><p>The most prominent examples of covering problems are the <a href="Set_cover_problem" title="Set cover problem">set cover problem</a>, which is equivalent to the <a href="Hitting_set" class="mw-redirect" title="Hitting set">hitting set problem</a>, and its special cases, the <a href="Vertex_cover_problem" class="mw-redirect" title="Vertex cover problem">vertex cover problem</a> and the <a href="Edge_cover_problem" class="mw-redirect" title="Edge cover problem">edge cover problem</a>.

</p><p>Covering problems allow the covering primitives to overlap; the process of covering something with non-overlapping primitives is called <a href="Decomposition_(disambiguation)" class="mw-disambig" title="Decomposition (disambiguation)">decomposition</a>.

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1246091330">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><table class="sidebar nomobile nowraplinks"><tbody><tr><th class="sidebar-title" style="font-size:130%;"><a href="Linear_programming#Covering/packing_dualities" title="Linear programming">Covering/packing-problem pairs</a></th></tr><tr><td class="sidebar-content">

<table style="width:100%;border-collapse:collapse;border-spacing:0px 0px;border:none;display:block;margin-top:0.4em;"><tbody><tr style="vertical-align:top"><td style="font-weight:bold;background:#ddf;text-align:center;border:1px #fafafa solid;"> </td><td style="font-weight:bold;background:#ddf;text-align:center;border:1px #fafafa solid;"> <a href="Packing_problems" title="Packing problems">Packing problems</a></td></tr><tr style="vertical-align:top"><td style="padding-top:0.15em;"> <a href="Set_cover_problem" title="Set cover problem">Minimum set cover</a></td><td style="padding-top:0.15em;"> <a href="Set_packing" title="Set packing">Maximum set packing</a></td></tr><tr style="vertical-align:top"><td> <a href="Edge_cover" title="Edge cover">Minimum edge cover</a></td><td> <a href="Matching_(graph_theory)" title="Matching (graph theory)">Maximum matching</a></td></tr><tr style="vertical-align:top"><td> <a href="Vertex_cover" title="Vertex cover">Minimum vertex cover</a></td><td> <a href="Independent_set_(graph_theory)" title="Independent set (graph theory)">Maximum independent set</a></td></tr><tr style="vertical-align:top"><td> <a href="Bin_covering_problem" title="Bin covering problem">Bin covering</a></td><td> <a href="Bin_packing_problem" title="Bin packing problem">Bin packing</a></td></tr><tr style="vertical-align:top"><td> <a href="Polygon_covering" title="Polygon covering">Polygon covering</a></td><td> <a href="Rectangle_packing" title="Rectangle packing">Rectangle packing</a></td></tr></tbody></table></td>

</tr><tr><td class="sidebar-navbar"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="General_linear_programming_formulation">General linear programming formulation</h2></div>

<p>In the context of <a href="Linear_programming" title="Linear programming">linear programming</a>, one can think of any minimization linear program as a covering problem if the coefficients in the constraint <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrix</a>, the objective function, and right-hand side are nonnegative.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> More precisely, consider the following general <a href="Integer_linear_program" class="mw-redirect" title="Integer linear program">integer linear program</a>:

</p>

<table>

<td>minimize

</td>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{n}c_{i}x_{i}}</annotation>

</semantics>

</math></span><img src="./a37a8d9469b1503805a581a834511dd4520ba2bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:7.678ex; height:6.843ex;" alt="{\displaystyle \sum _{i=1}^{n}c_{i}x_{i}}" loading="lazy"></span>

</td></tr>

<tr>

<td>subject to

</td>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{n}a_{ji}x_{i}\geq b_{j}{\text{ for }}j=1,\dots ,m}</annotation>

</semantics>

</math></span><img src="./cf31b5e8f24cc1fd94d197050a8d515874592042.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:29.969ex; height:6.843ex;" alt="{\displaystyle \sum _{i=1}^{n}a_{ji}x_{i}\geq b_{j}{\text{ for }}j=1,\dots ,m}" loading="lazy"></span>

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}\in \left\{0,1,2,\ldots \right\}{\text{ for }}i=1,\dots ,n}</annotation>

</semantics>

</math></span><img src="./914b5dc2295c73d05ced6bf3c744f6bf7c6e0a96.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.578ex; height:2.843ex;" alt="{\displaystyle x_{i}\in \left\{0,1,2,\ldots \right\}{\text{ for }}i=1,\dots ,n}" loading="lazy"></span>.

</td></tr></tbody></table>

<p>Such an integer linear program is called a <b>covering problem</b> if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{ji},b_{j},c_{i}\geq 0}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{ji},b_{j},c_{i}\geq 0}</annotation>

</semantics>

</math></span><img src="./404ea73dbcce910df0aec8908f56ec9e6d4bffb7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.75ex; height:2.843ex;" alt="{\displaystyle a_{ji},b_{j},c_{i}\geq 0}" loading="lazy"></span> for all <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=1,\dots ,n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=1,\dots ,n}</annotation>

</semantics>

</math></span><img src="./f3f269b2f3b2f87fec0168426652a5ea80b56112.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.636ex; height:2.509ex;" alt="{\displaystyle i=1,\dots ,n}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=1,\dots ,m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=1,\dots ,m}</annotation>

</semantics>

</math></span><img src="./ca9db78e9917872c0f5e97636b351f5a6b4e9d38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:12.464ex; height:2.509ex;" alt="{\displaystyle j=1,\dots ,m}" loading="lazy"></span>.

</p><p><b>Intuition:</b> Assume having <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> types of object and each object of type <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span> has an associated cost of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}}</annotation>

</semantics>

</math></span><img src="./01acb7953ba52c2aa44264b5d0f8fd223aa178a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.807ex; height:2.009ex;" alt="{\displaystyle c_{i}}" loading="lazy"></span>. The number <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math></span><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"></span> indicates how many objects of type <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span> we buy. If the constraints <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\mathbf {x} \geq \mathbf {b} }">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\mathbf {x} \geq \mathbf {b} }</annotation>

</semantics>

</math></span><img src="./9eab646d27dfcddee4fa8381613db1c6e649a8c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.738ex; height:2.343ex;" alt="{\displaystyle A\mathbf {x} \geq \mathbf {b} }" loading="lazy"></span> are satisfied, it is said that <i><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} }</annotation>

</semantics>

</math></span><img src="./32adf004df5eb0a8c7fd8c0b6b7405183c5a5ef2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.411ex; height:1.676ex;" alt="{\displaystyle \mathbf {x} }" loading="lazy"></span> is a covering</i> (the structures that are covered depend on the combinatorial context). Finally, an optimal solution to the above integer linear program is a covering of minimal cost.

</p>

<div class="mw-heading mw-heading2"><h2 id="Kinds_of_covering_problems">Kinds of covering problems</h2></div>

<p>There are various kinds of covering problems in <a href="Graph_theory" title="Graph theory">graph theory</a>, <a href="Computational_geometry" title="Computational geometry">computational geometry</a> and more; see Category:Covering problems. Other stochastic related versions of the problem can be found.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Covering_in_Petri_nets">Covering in Petri nets</h3></div>

<p>For <a href="Petri_net" title="Petri net">Petri nets</a>, the covering problem is defined as the question if for a given marking, there exists a run of the net, such that some larger (or equal) marking can be reached. <i>Larger</i> means here that all components are at least as large as the ones of the given marking and at least one is properly larger.

</p>

<div class="mw-heading mw-heading3"><h3 id="Rainbow_covering">Rainbow covering</h3></div>

<p>In some covering problems, the covering should satisfy some additional requirements. In particular, in the <b>rainbow covering</b> problem, each of the original objects has a "color", and it is required that the covering contains exactly one (or at most one) object of each color. Rainbow covering was studied e.g. for covering points by <a href="Interval_(mathematics)" title="Interval (mathematics)">intervals</a>:<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li>There is a set <i>J</i> of <i>n</i> colored intervals on the <a href="Real_line" class="mw-redirect" title="Real line">real line</a>, and a set <i>P</i> of points on the real line.</li>

<li>A <a href="Subset" title="Subset">subset</a> <i>Q</i> of <i>J</i> is called a <i>rainbow set</i> if it contains at most a single interval of each color.</li>

<li>A set of intervals <i>J</i> is called a <i>covering</i> of <i>P</i> if each point in <i>P</i> is contained in at least one interval of <i>Q</i>.</li>

<li>The <i>Rainbow covering problem</i> is the problem of finding a rainbow set <i>Q</i> that is a covering of <i>P</i>.</li></ul>

<p>The problem is <a href="NP-hardness" title="NP-hardness">NP-hard</a> (by reduction from <a href="Linear_SAT" class="mw-redirect" title="Linear SAT">linear SAT</a>).

</p>

<div class="mw-heading mw-heading3"><h3 id="Conflict-free_covering">Conflict-free covering</h3></div>

<p>A more general notion is <b>conflict-free covering</b>.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> In this problem:

</p>

<ul><li>There is a set <i>O</i> of <i>m</i> objects, and a conflict-graph <i>G<sub>O</sub></i> on <i>O</i>.</li>

<li>A subset <i>Q</i> of <i>O</i> is called <i>conflict-free</i> if it is an <a href="Independent_set_(graph_theory)" title="Independent set (graph theory)">independent set</a> in <i>G<sub>O</sub></i>, that is, no two objects in <i>Q</i> are connected by an edge in <i>G<sub>O</sub></i>.</li>

<li>A rainbow set is a conflict-free set in the special case in which <i>G<sub>O</sub></i> is made of disjoint cliques, where each clique represents a color.</li></ul>

<p><i>Conflict-free set cover</i> is the problem of finding a conflict-free subset of <i>O</i> that is a covering of <i>P</i>. Banik, Panolan, Raman, Sahlot and Saurabh<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> <a href="Mathematical_proof" title="Mathematical proof">prove</a> the following for the special case in which the conflict-graph has bounded <a href="Arboricity" title="Arboricity">arboricity</a>:

</p>

<ul><li>If the geometric cover problem is <a href="Fixed-parameter_algorithm" class="mw-redirect" title="Fixed-parameter algorithm">fixed-parameter</a> tractable (FPT), then the conflict-free geometric cover problem is FPT.</li>

<li>If the geometric cover problem admits an r-approximation algorithm, then the conflict-free geometric cover problem admits a similar approximation algorithm in FPT time.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFVazirani2001" class="citation book cs1"><a href="Vijay_Vazirani" title="Vijay Vazirani">Vazirani, Vijay V.</a> (2001). <i>Approximation Algorithms</i>. Springer-Verlag. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-65367-8</bdi>.</cite><sup class="reference nowrap"><span title="Page / location: 112">: 112 </span></sup></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFDouek-Pinkovich,_Y.,_Ben-Gal,_I.,_&_Raviv,_T._(2022)" class="citation web cs1">Douek-Pinkovich, Y., Ben-Gal, I., & Raviv, T. (2022). <a rel="nofollow" class="external text" href="http://www.eng.tau.ac.il/~bengal/STCP.pdf">"The Stochastic Test Collection Problem: Models, Exact and Heuristic Solution Approaches"</a> <span class="cs1-format">(PDF)</span>. European Journal of Operational Research, 299 (2022), 945–959}.</cite><span class="cs1-maint citation-comment"><code class="cs1-code">{{cite web}}</code>: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)</span></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFAjtai1973" class="citation cs2"><a href="Mikl%C3%B3s_Ajtai" title="Miklós Ajtai">Ajtai, Miklós</a> (1973), "The solution of a problem of T. Radó", <i>Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques</i>, <b>21</b>: <span class="nowrap">61–</span>63, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0319053">0319053</a></cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFBeregDumitrescuJiang2010" class="citation cs2">Bereg, Sergey; Dumitrescu, Adrian; Jiang, Minghui (2010), "On covering problems of Rado", <i>Algorithmica</i>, <b>57</b> (3): <span class="nowrap">538–</span>561, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00453-009-9298-z">10.1007/s00453-009-9298-z</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2609053">2609053</a></cite>; preliminary announcement in <a href="SWAT_and_WADS_conferences" title="SWAT and WADS conferences">SWAT 2008</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-69903-3_27">10.1007/978-3-540-69903-3_27</a></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFArkinBanikCarmiCitovsky2018" class="citation journal cs1">Arkin, Esther M.; Banik, Aritra; Carmi, Paz; Citovsky, Gui; Katz, Matthew J.; Mitchell, Joseph S. B.; Simakov, Marina (2018-12-11). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.dam.2018.05.011">"Selecting and covering colored points"</a>. <i>Discrete Applied Mathematics</i>. <b>250</b>: <span class="nowrap">75–</span>86. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.dam.2018.05.011">10.1016/j.dam.2018.05.011</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0166-218X">0166-218X</a>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFBanikSahlotSaurabh2020" class="citation journal cs1">Banik, Aritra; Sahlot, Vibha; Saurabh, Saket (2020-08-01). <a rel="nofollow" class="external text" href="http://www.sciencedirect.com/science/article/pii/S0925772119301324">"Approximation algorithms for geometric conflict free covering problems"</a>. <i>Computational Geometry</i>. <b>89</b>: 101591. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.comgeo.2019.101591">10.1016/j.comgeo.2019.101591</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0925-7721">0925-7721</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:209959954">209959954</a>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFBanikPanolanRamanSahlot2020" class="citation journal cs1">Banik, Aritra; Panolan, Fahad; Raman, Venkatesh; Sahlot, Vibha; Saurabh, Saket (2020-01-01). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/s00453-019-00600-w">"Parameterized Complexity of Geometric Covering Problems Having Conflicts"</a></span>. <i>Algorithmica</i>. <b>82</b> (1): <span class="nowrap">1–</span>19. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00453-019-00600-w">10.1007/s00453-019-00600-w</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1432-0541">1432-0541</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:254027914">254027914</a>.</cite></span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-30" href="https://en.wikipedia.org/wiki/?title=Covering_problems&oldid=1298079781">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>